package com.leetcode.dfs;


public class Leetcode124 {
    private int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getPath(root);
        return res;
    }

    private int getPath(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftPath = Math.max(0, getPath(node.left));
        int rightPath = Math.max(0, getPath(node.right));
        res = Math.max(res, leftPath + rightPath + node.val);

        // .....
        return Math.max(leftPath + node.val, rightPath + node.val);
    }
}
